import TreeTraversal.TreeNode;

public class maxPathSum3 {
    int max = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        max(root);
        return max;
    }
    public int max(TreeNode root){
        if(root == null){
            return 0;
        }
        int left = Math.max(max(root.left),0);
        int right = Math.max(max(root.right),0);
        int a = root.val + left + right;
        max = Math.max(a,max);
        return root.val + Math.max(left,right);
    }
}
